package albero;

import java.util.Iterator;
import java.util.LinkedList;

public class BTree<E> implements Tree<E>{

	private BNode<E> root;
	private int size;
	
	public BTree(){
		root = null;
		size = 0;
	}
	
	// O(1)
	public BNode<E> addRoot(E e){
		if (!isEmpty())
			throw new RuntimeException("L'albero ha gia una radice");
		BNode<E> r = new BNode<E>(e, null);
		root = r;
		size++;
		return r;
	}
	
	// O(1)
	public int size(){
		return size;
	}
	
	// O(1)
	public boolean isEmpty(){
		return root == null;
	}
	
	// O(n)
	public Iterator<E> iterator(){
		return iterator(root, new LinkedList<E>()).listIterator();
	}
	
	private LinkedList<E> iterator(BNode<E> v, LinkedList<E> l){
		l.add(v.getElement());
		if (hasLeft(v))
			l = iterator(v.getLeft(), l);
		if (hasRight(v))
			l = iterator(v.getRight(), l);
		return l;
	}
	
	// O(n)
	public Iterable<Node<E>> nodes(){
		return nodes(root, new LinkedList<Node<E>>());
	}
	
	private LinkedList<Node<E>> nodes(BNode<E> v, LinkedList<Node<E>> l){
		l.add(v);
		if (hasLeft(v))
			l = nodes(v.getLeft(), l);
		if (hasRight(v))
			l = nodes(v.getRight(), l);
		return l;
	}
	
	// O(1)
	public BNode<E> insertLeft(BNode<E> v, E e){
		BNode<E> l = new BNode<E>(e, v);
		v.setLeft(l);
		size++;
		return l;
	}
	
	// O(1)
	public boolean hasLeft(BNode<E> v){
		return v.getLeft() != null;
	}
		
	// O(1)
	public BNode<E> insertRight(BNode<E> v, E e){
		BNode<E> r = new BNode<E>(e, v);
		v.setRight(r);
		size++;
		return r;
	}
	
	// O(1)
	public boolean hasRight(BNode<E> v){
		return v.getRight() != null;
	}
	
	// O(1)
	public E remove(BNode<E> v){
		if (v.getLeft() != null && v.getRight() != null)
			throw new RuntimeException("Non posso rimuovere un nodo con due figli");
		BNode<E> sost;		//sostituto
		if (v.getLeft() != null)
			sost = v.getLeft();
		else if (v.getRight() != null)
			sost = v.getRight();
		else
			sost = null;
		if (v == root){		//caso particolare della radice
			if (sost != null)
				sost.setParent(null);
			root = sost;
		}
		else {
			BNode<E> par = v.getParent();		//parent
			if (par.getLeft() == v)
				par.setLeft(sost);
			else
				par.setRight(sost);
			if (sost != null)
				sost.setParent(par);
		}
		size--;
		return v.getElement();
	}

	// O(1)
	public E replace(Node<E> v, E e){
		E temp = v.getElement();
		v.setElement(e);
		return temp;
	}
	
	// O(1)
	public Node<E> root(){
		if (isEmpty()) throw new RuntimeException("L'albero non ha radice");
		return root;
	}
	
	// O(1)
	public Node<E> parent(Node<E> v){
		return v.getParent();
	}
	
	// O(deg(v))
	public Iterable<Node<E>> children(Node<E> v){
		return v.getChildren();
	}
	
	// O(1)
	public boolean isInternal(Node<E> v){
		return v.getChildren().size() != 0;
	}
	
	// O(1)
	public boolean isExternal(Node<E> v){
		return !isInternal(v);
	}
	
	// O(1)
	public boolean isRoot(Node<E> v){
		return v == root;
	}
	
	
	/**
	 * Metodo che permette di cambiare la root dell'albero.
	 * Utile nella costruzione bottomUP.
	 * @param newRoot
	 * @return
	 */
	public BNode<E> changeRoot(E e) {
		BNode<E> r = new BNode<E>(e, null);
		BNode<E> oldRoot = this.root;
		root = r;
		oldRoot.setParent(root);
		root.setRight(oldRoot);
		size++;		
		return root;
	}
	
}
